// 剑指 Offer 42. 连续子数组的最大和
// 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

// 要求时间复杂度为O(n) 。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  // 计算每个f(i)的最大值
  let n = nums.length
  let sum = nums[0]
  for (let i = 1; i < n; i++) {
    if(nums[i-1]>= 0 ){
      nums[i] = nums[i-1] + nums[i]
    }
    sum = Math.max(sum,nums[i])
  }
  return sum
};
var nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
console.log(maxSubArray(nums))
